package com.leetcode.algorithm.y22.m09.w2;

/**
 * 1706. 球会落何处
 * 
 * https://leetcode.cn/problems/where-will-the-ball-fall/
 * 
 * @author jie.deng
 *
 */
class Question1706Solution01 {

	public int[] findBall(int[][] grid) {
		// DFS
		int m = grid.length;
		int n = grid[0].length;
		if (n == 1) {
			return new int[] { -1 };
		}
		int[] ans = new int[n];
		for (int initCol = 0; initCol < n; initCol++) {
			int col = initCol;
			for (int row = 0; row < m; row++) {
				if (grid[row][col] == 1 && (col < n - 1 && grid[row][col + 1] == 1)) {
					col++;
				} else if (grid[row][col] == -1 && (col > 0 && grid[row][col - 1] == -1)) {
					col--;
				} else {
					col = -1;
					break;
				}
			}
			ans[initCol] = col;
		}
		return ans;
	}

}